1. Technical Field
The present disclosure relates to methods and apparatuses for optimization. More specifically, the present disclosure relates to methods and apparatuses for evolutionary computing based optimization.
2. Related Art
Evolutionary computing based optimization techniques (ECBOTs) are based on the processes of natural evolution. In the past twenty years, researchers have successfully applied ECBOTs to a large array of problems from industrial, electrical, computer, civil and environmental engineering; aeronautics; finance; chemistry; medicine; physics and computer science. However, such studies have traditionally concentrated on problems involving two or three objectives.
While multi-objective applications are growing in their success, there exists strong theoretical and experimental evidence suggesting existing approaches (e.g., evolutionary approaches that are capable of tackling two or three objectives) are insufficient for multi-objective problems. Some studies have observed that the proportion of locally non-dominated solutions tends to become large as the number of objectives increases. This tendency is termed dominance resistance. Other studies show theoretically that dominance resistance can cause the convergence rate of ECBOTs to degrade to be no better than random search for problems with ten or more objectives.
Specifically, a study entitled “Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems,” by authors Ishibuchi, H., Tsukamoto, N., Hitotsuyanagi, Y., and Nojima, Y., showed that several state-of-the-art evolutionary approaches fail on problems with as few as four objectives. This study was published on pages 649-656 of the conference proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008), New York, N.Y., USA.
Further, some studies have observed that the selection mechanism promoting diverse solutions along the entire extent of the tradeoff surface can cause deterioration. Deterioration occurs whenever the solution set discovered by an ECBOT at time i contains one or more solutions dominated by a solution discovered at some earlier point in time j<i. In the extreme, deterioration can cause an ECBOT to diverge away from the Pareto front. Many state-of-the-art ECBOTs in use today are not capable of avoiding deterioration.
Recently, studies have attempted to rectify these issues by improving various components of ECBOTs. One such approach attempts to eliminate dominance resistance by utilizing more stringent dominance relations. These studies tend to focus on the “knee” region of the Pareto front and fail to produce solutions along the entire extent of the tradeoff surface.